//给你一个下标从 0 开始的 正 整数数组 nums 。你可以对数组执行以下操作 任意 次： 
//
// 
// 选择一个满足 0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数。 
// 
//
// 请你返回使数组 nums 中所有元素都等于 1 的 最少 操作次数。如果无法让数组全部变成 1 ，请你返回 -1 。 
//
// 两个正整数的最大公约数指的是能整除这两个数的最大正整数。 
//
// 
//
// 示例 1： 
//
// 输入：nums = [2,6,3,4]
//输出：4
//解释：我们可以执行以下操作：
//- 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。
//- 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。
//- 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。
//- 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。
// 
//
// 示例 2： 
//
// 输入：nums = [2,10,6,14]
//输出：-1
//解释：无法将所有元素都变成 1 。
// 
//
// 
//
// 提示： 
//
// 
// 2 <= nums.length <= 50 
// 1 <= nums[i] <= 10⁶ 
// 
//
// Related Topics 数组 数学 数论 👍 57 👎 0


package LeetCode.editor.cn;



/**
 * @author ldltd
 * @date 2025-11-12 18:52:18
 * @description 2654.使数组所有元素变成 1 的最少操作次数
 */
public class MinimumNumberOfOperationsToMakeAllArrayElementsEqualTo1{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 MinimumNumberOfOperationsToMakeAllArrayElementsEqualTo1 fun=new MinimumNumberOfOperationsToMakeAllArrayElementsEqualTo1();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 // 如果能一次凑出来一个1，则操作数就是数组长度
		 // 那问题变成了，怎么在数组中最快凑出一个1来
    // 如果所有数字的gcd都大于1，那么怎么都凑不出1，如果已经有1，那么就直接返回数组长度减去1
    // 如果不属于上面的，就找到一个最小 的区间，使得这个区间的gcd是1，
    // 假设 这个区间是[i,j]，那么这个区间的gcd就是这个区间的元素得到1的次数是minLen-1，
    // 再由这个1 操作其他数，需要 n-1，所以操作数就是 n-1+minLen-1=minLen+n-2
    // 找到这个最小的区间
    // 按照区间长度从小到大枚举所有区间，然后依次计算它们的 gcd。

    public int minOperations(int[] nums) {
        int n = nums.length;
        // 统计1的个数
        int num1 = 0;
        // 统计gcd
        int g = 0;
        for (int x : nums) {
            if (x == 1) {
                num1++;
            }
            g = gcd(g, x);
        }
        if (num1 > 0) {
            return n - num1;
        }
        if (g > 1) {
            return -1;
        }

        int minLen = n;
        for (int i = 0; i < n; i++) {
            int currentGcd = 0;
            for (int j = i; j < n; j++) {
                currentGcd = gcd(currentGcd, nums[j]);
                if (currentGcd == 1) {
                    minLen = Math.min(minLen, j - i + 1);
                    break;
                }
            }
        }
        return minLen + n - 2;
    }
     int gcd(int a,int b){
        return b!=0?gcd(b,a%b):a;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
